@inproceedings{CarbonellG98,
  author    = {Jaime G. Carbonell and
               Jade Goldstein},
  title     = {The Use of MMR, Diversity-Based Reranking for Reordering
               Documents and Producing Summaries},
  booktitle = {SIGIR},
  year      = {1998},
  pages     = {335-336}
}

@inproceedings{McNeeRK06,
  author    = {Sean M. McNee and
               John Riedl and
               Joseph A. Konstan},
  title     = {Being accurate is not enough: how accuracy metrics have
               hurt recommender systems},
  booktitle = {CHI Extended Abstracts},
  year      = {2006},
  pages     = {1097-1101}
}

@inproceedings{BansalS06,
  author    = {Nikhil Bansal and
               Maxim Sviridenko},
  title     = {The {Santa Claus} problem},
  booktitle = {STOC},
  year      = {2006},
  pages     = {31-40},
  ee        = {http://doi.acm.org/10.1145/1132516.1132522},
  crossref  = {DBLP:conf/stoc/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DevanurJSW11,
  author    = {Nikhil R. Devanur and
               Kamal Jain and
               Balasubramanian Sivan and
               Christopher A. Wilkens},
  title     = {Near optimal online algorithms and fast approximation algorithms
               for resource allocation problems},
  booktitle = {ACM Conference on Electronic Commerce},
  year      = {2011},
  pages     = {29-38},
  ee        = {http://doi.acm.org/10.1145/1993574.1993581},
  crossref  = {DBLP:conf/sigecom/2011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{YuLA09a,
  author    = {Cong Yu and
               Laks V. S. Lakshmanan and
               Sihem Amer-Yahia},
  title     = {Recommendation Diversification Using Explanations},
  booktitle = {ICDE},
  year      = {2009},
  pages     = {1299-1302}
}

@inproceedings{YuLA09b,
  author    = {Cong Yu and
               Laks V. S. Lakshmanan and
               Sihem Amer-Yahia},
  title     = {It takes variety to make a world: diversification in recommender
               systems},
  booktitle = {EDBT},
  year      = {2009},
  pages     = {368-378}
}

@inproceedings{VeeSSBA08,
  author    = {Erik Vee and
               Utkarsh Srivastava and
               Jayavel Shanmugasundaram and
               Prashant Bhat and
               Sihem Amer-Yahia},
  title     = {Efficient Computation of Diverse Query Results},
  booktitle = {ICDE},
  year      = {2008}
}

@inproceedings{ZieglerMKL05,
  author    = {Cai-Nicolas Ziegler and
               Sean M. McNee and
               Joseph A. Konstan and
               Georg Lausen},
  title     = {Improving recommendation lists through topic diversification},
  booktitle = {WWW},
  year      = {2005},
  pages     = {22-32}
}

@article{ZhaiL06,
  author    = {ChengXiang Zhai and
               John D. Lafferty},
  title     = {A risk minimization framework for information retrieval},
  journal   = {Inf. Process. Manage.},
  volume    = {42},
  number    = {1},
  year      = {2006},
  pages     = {31-55}
}

@inproceedings{AgrawalGHI09,
  author    = {Rakesh Agrawal and
               Sreenivas Gollapudi and
               Alan Halverson and
               Samuel Ieong},
  title     = {Diversifying search results},
  booktitle = {WSDM},
  year      = {2009},
  pages     = {5-14}
}

@article{DrosouP09,
  author    = {Marina Drosou and
               Evaggelia Pitoura},
  title     = {Diversity over Continuous Data},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {32},
  number    = {4},
  year      = {2009},
  pages     = {49-56}
}

@article{DrosouP10,
  author    = {Marina Drosou and
               Evaggelia Pitoura},
  title     = {Search result diversification},
  journal   = {SIGMOD Record},
  volume    = {39},
  number    = {1},
  year      = {2010},
  pages     = {41-47}
}

@inproceedings{SantosMO10cikm,
  author    = {Rodrygo L. T. Santos and
               Craig Macdonald and
               Iadh Ounis},
  title     = {Selectively diversifying web search results},
  booktitle = {CIKM},
  year      = {2010},
  pages     = {1179-1188}
}

@inproceedings{SantosMO10www,
  author    = {Rodrygo L. T. Santos and
               Craig Macdonald and
               Iadh Ounis},
  title     = {Exploiting query reformulations for web search result diversification},
  booktitle = {WWW},
  year      = {2010},
  pages     = {881-890}
}

@inproceedings{SantosMO11b,
  author    = {Rodrygo L. T. Santos and
               Craig Macdonald and
               Iadh Ounis},
  title     = {How diverse are web search results?},
  booktitle = {SIGIR},
  year      = {2011},
  pages     = {1187-1188}
}

@inproceedings{SantosMO11a,
  author    = {Rodrygo L. T. Santos and
               Craig Macdonald and
               Iadh Ounis},
  title     = {Intent-aware search result diversification},
  booktitle = {SIGIR},
  year      = {2011},
  pages     = {595-604}
}

@inproceedings{GollapudiS09,
  author    = {Sreenivas Gollapudi and
               Aneesh Sharma},
  title     = {An axiomatic approach for result diversification},
  booktitle = {WWW},
  year      = {2009},
  pages     = {381-390}
}

@article{RadlinskiBCJ09,
  author    = {Filip Radlinski and
               Paul N. Bennett and
               Ben Carterette and
               Thorsten Joachims},
  title     = {Redundancy, diversity and interdependent document relevance},
  journal   = {SIGIR Forum},
  volume    = {43},
  number    = {2},
  year      = {2009},
  pages     = {46-52}
}

@inproceedings{SlivkinsRG10,
  author    = {Aleksandrs Slivkins and
               Filip Radlinski and
               Sreenivas Gollapudi},
  title     = {Learning optimally diverse rankings over large document
               collections},
  booktitle = {ICML},
  year      = {2010},
  pages     = {983-990}
}

@inproceedings{AdlerBST01,
 author = {M. Adler and T. Bu and R. Sitaraman and D. Towsley},
 title = {Tree layout for internal network characterizations in multicast networks},
 booktitle = {Proceedings of NGC},
 year ={2001},
 address = {London, UK},
 month = {Nov}
}

@techreport{AgrawalNR06,
    author="S. Agrawal and K. V. M. Naidu and R. Rastogi",
    title="Efficient Detection of Distributed Constraint Violations",
    institution="Bell Labs Technical Memorandum",
    number="ITD-05-46578D",
    year="2006",
}

@article{AlonAABN06,
  author    = {Noga Alon and
               Baruch Awerbuch and
               Yossi Azar and
               Niv Buchbinder and
               Joseph Naor},
  title     = {A general approach to online network optimization problems},
  journal   = {ACM Transactions on Algorithms},
  volume    = {2},
  number    = {4},
  year      = {2006},
  pages     = {640-660},
  ee        = {http://doi.acm.org/10.1145/1198513.1198522},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{AlonAABN09,
  author    = {Noga Alon and
               Baruch Awerbuch and
               Yossi Azar and
               Niv Buchbinder and
               Joseph Naor},
  title     = {The Online Set Cover Problem},
  journal   = {SIAM J. Comput.},
  volume    = {39},
  number    = {2},
  year      = {2009},
  pages     = {361-370},
  ee        = {http://dx.doi.org/10.1137/060661946},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{AlonAG09,
  author    = {Noga Alon and
               Yossi Azar and
               Shai Gutner},
  title     = {Admission control to minimize rejections and online set
               cover with repetitions},
  journal   = {ACM Transactions on Algorithms},
  volume    = {6},
  number    = {1},
  year      = {2009},
  ee        = {http://doi.acm.org/10.1145/1644015.1644026},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{AlthausCMPTZ06,
  author    = {Ernst Althaus and
               Gruia Calinescu and
               Ion I. Mandoiu and
               Sushil K. Prasad and
               N. Tchervenski and
               Alexander Zelikovsky},
  title     = {Power Efficient Range Assignment for Symmetric Connectivity
               in Static Ad Hoc Wireless Networks},
  journal   = {Wireless Networks},
  volume    = {12},
  number    = {3},
  year      = {2006},
  pages     = {287-299},
  ee        = {http://dx.doi.org/10.1007/s11276-005-5275-x},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{AspnesAFPW97,
  author    = {James Aspnes and
               Yossi Azar and
               Amos Fiat and
               Serge A. Plotkin and
               Orli Waarts},
  title     = {On-line routing of virtual circuits with applications to
               load balancing and machine scheduling},
  journal   = {J. ACM},
  volume    = {44},
  number    = {3},
  year      = {1997},
  pages     = {486-504},
  ee        = {http://doi.acm.org/10.1145/258128.258201},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{AwerbuchAFL96,
  author    = {Baruch Awerbuch and
               Yossi Azar and
               Amos Fiat and
               Frank Thomson Leighton},
  title     = {Making Commitments in the Face of Uncertainty: How to Pick
               a Winner Almost Every Time (Extended Abstract)},
  booktitle = {STOC},
  year      = {1996},
  pages     = {519-530},
  ee        = {http://doi.acm.org/10.1145/237814.238000},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Azar96,
  author    = {Yossi Azar},
  title     = {On-line Load Balancing},
  booktitle = {Online Algorithms},
  year      = {1996},
  pages     = {178-195},
  ee        = {http://dx.doi.org/10.1007/BFb0029569},
  crossref  = {DBLP:conf/dagstuhl/1996oa},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{AzarNR95,
  author    = {Yossi Azar and
               Joseph Naor and
               Raphael Rom},
  title     = {The Competitiveness of On-Line Assignments},
  journal   = {J. Algorithms},
  volume    = {18},
  number    = {2},
  year      = {1995},
  pages     = {221-237},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Bang-jensenFJ95,
  author    = {J{\o}rgen Bang-Jensen and
               Andr{\'a}s Frank and
               Bill Jackson},
  title     = {Preserving and Increasing Local Edge-Connectivity in Mixed
               Graphs},
  journal   = {SIAM J. Discrete Math.},
  volume    = {8},
  number    = {2},
  year      = {1995},
  pages     = {155-178},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/22698},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Bang-JensenJ00,
  author    = {J{\o}rgen Bang-Jensen and
               Tibor Jord{\'a}n},
  title     = {Splitting Off Edges within a Specified Subset Preserving
               the Edge-Connectivity of the Graph},
  journal   = {J. Algorithms},
  volume    = {37},
  number    = {2},
  year      = {2000},
  pages     = {326-343},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Bang-JensenJ04,
  author    = {J{\o}rgen Bang-Jensen and
               Tibor Jord{\'a}n},
  title     = {Splitting off edges between two subsets preserving the edge-connectivity
               of the graph},
  journal   = {Discrete Mathematics},
  volume    = {276},
  number    = {1-3},
  year      = {2004},
  pages     = {5-28},
  ee        = {http://dx.doi.org/10.1016/S0012-365X(03)00291-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BansalBN07,
  author    = {Nikhil Bansal and
               Niv Buchbinder and
               Joseph Naor},
  title     = {A Primal-Dual Randomized Algorithm for Weighted Paging},
  booktitle = {FOCS},
  year      = {2007},
  pages     = {507-517},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.7},
  crossref  = {DBLP:conf/focs/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BansalBGN07,
  author    = {Nikhil Bansal and
               Niv Buchbinder and
               Anupam Gupta and
               Joseph Naor},
  title     = {An {\it } (log$^{\mbox{2}}$ {\it } )-Competitive Algorithm
               for Metric Bipartite Matching},
  booktitle = {ESA},
  year      = {2007},
  pages     = {522-533},
  ee        = {http://dx.doi.org/10.1007/978-3-540-75520-3_47},
  crossref  = {DBLP:conf/esa/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{BansalBN08,
  author    = {Nikhil Bansal and
               Niv Buchbinder and
               Joseph Naor},
  title     = {Randomized competitive algorithms for generalized caching},
  booktitle = {STOC},
  year      = {2008},
  pages     = {235-244},
  ee        = {http://doi.acm.org/10.1145/1374376.1374412},
  crossref  = {DBLP:conf/stoc/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BartalFKV95,
  author    = {Yair Bartal and
               Amos Fiat and
               Howard J. Karloff and
               Rakesh Vohra},
  title     = {New Algorithms for an Ancient Scheduling Problem},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {51},
  number    = {3},
  year      = {1995},
  pages     = {359-366},
  ee        = {http://dx.doi.org/10.1006/jcss.1995.1074},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BatsonSS09,
  author    = {Joshua D. Batson and
               Daniel A. Spielman and
               Nikhil Srivastava},
  title     = {Twice-ramanujan sparsifiers},
  booktitle = {STOC},
  year      = {2009},
  pages     = {255-262},
  ee        = {http://doi.acm.org/10.1145/1536414.1536451},
  crossref  = {DBLP:conf/stoc/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Benczur95,
  author    = {Andr{\'a}s A. Bencz{\'u}r},
  title     = {Counterexamples for Directed and Node Capacitated Cut-Trees},
  journal   = {SIAM J. Comput.},
  volume    = {24},
  number    = {3},
  year      = {1995},
  pages     = {505-510},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BenczurK96,
  author    = {Andr{\'a}s A. Bencz{\'u}r and
               David R. Karger},
  title     = {Approximating {\it s-t} Minimum Cuts in $\tilde{O}(n^2)$
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {47-55},
  ee        = {http://doi.acm.org/10.1145/237814.237827},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{bejerano03,
  author    = {Yigal Bejerano and
               Rajeev Rastogi},
  title     = {Robust Monitoring of Link Delays and Faults in {IP} Networks},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2003},
}

@article{BhalgatHKP08,
  author    = {Anand Bhalgat and
               Ramesh Hariharan and
               Telikepalli Kavitha and
               Debmalya Panigrahi},
  title     = {Fast Edge Splitting and Edmonds' Arborescence Construction for
               Unweighted Graphs},
  booktitle = {Pre-print}
}

@inproceedings{BhalgatHKP07,
  author    = {Anand Bhalgat and
               Ramesh Hariharan and
               Telikepalli Kavitha and
               Debmalya Panigrahi},
  title     = {An {\~O}(mn) Gomory-Hu tree construction algorithm for
               unweighted graphs},
  booktitle = {STOC},
  year      = {2007},
  pages     = {605-614},
  ee        = {http://doi.acm.org/10.1145/1250790.1250879},
  crossref  = {DBLP:conf/stoc/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BirmanCR09,
  author    = {Ken Birman and
               Gregory Chockler and
               Robbert van Renesse},
  title     = {Toward a cloud computing research agenda},
  journal   = {SIGACT News},
  volume    = {40},
  number    = {2},
  year      = {2009},
  pages     = {68-80},
  ee        = {http://doi.acm.org/10.1145/1556154.1556172},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BiswasM05,
  author    = {Sanjit Biswas and
               Robert Morris},
  title     = {ExOR: opportunistic multi-hop routing for wireless networks},
  booktitle = {SIGCOMM},
  year      = {2005},
  pages     = {133-144},
  ee        = {http://doi.acm.org/10.1145/1080091.1080108},
  crossref  = {DBLP:conf/sigcomm/2005},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@book{Bollobas98,
	author		= {Bela Bollobas},
	title			= {Modern Graph Theory},
	publisher	= {Springer},
	year			= {1998},

@inproceedings{bontridder03,
 author = {K. M. J. de Bontridder and B. V. Halld\'orsson and M. M. Halld\'orsson and C. A. J. Hurkens and J. K. Lenstra and R. Ravi and L. Stougie},
 title = {Approximation algorithms for the test cover problem},
 booktitle = {Math. Program., 98(1-3, Ser. B)},
 year = {2003},
 pages = {477--491},
}

@inproceedings{breitbart00,
  author    = {Y. Breitbart and C. Y. Chan and M. Garofalakis and R. Rastogi and A. Silberschatz},
  title     = {Efficiently monitoring bandwidth and latency in {IP} networks},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2000}
}

@inproceedings{bu02,
 author = {Tian Bu and Nick Duffield and Francesco Lo Presti and Don Towsley},
 title = {Network tomography on general topologies},
 booktitle = {SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems},
 year = {2002},
 isbn = {1-58113-531-9},
 pages = {21--30},
 publisher = {ACM Press},
 address = {New York, NY, USA},
}

@inproceedings{BuchbinderJN07,
  author    = {Niv Buchbinder and
               Kamal Jain and
               Joseph Naor},
  title     = {Online Primal-Dual Algorithms for Maximizing Ad-Auctions
               Revenue},
  booktitle = {ESA},
  year      = {2007},
  pages     = {253-264},
  ee        = {http://dx.doi.org/10.1007/978-3-540-75520-3_24},
  crossref  = {DBLP:conf/esa/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BuchbinderKLMS08,
  author    = {Niv Buchbinder and
               Tracy Kimbrel and
               Retsef Levi and
               Konstantin Makarychev and
               Maxim Sviridenko},
  title     = {Online make-to-order joint replenishment model: primal dual
               competitive algorithms},
  booktitle = {SODA},
  year      = {2008},
  pages     = {952-961},
  ee        = {http://doi.acm.org/10.1145/1347082.1347186},
  crossref  = {DBLP:conf/soda/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BuchbinderN06a,
  author    = {Niv Buchbinder and
               Joseph Naor},
  title     = {Improved Bounds for Online Routing and Packing Via a Primal-Dual
               Approach},
  booktitle = {FOCS},
  year      = {2006},
  pages     = {293-304},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.39},
  crossref  = {DBLP:conf/focs/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{BuchbinderN06b,
  author    = {Niv Buchbinder and
               Joseph Naor},
  title     = {Fair online load balancing},
  booktitle = {SPAA},
  year      = {2006},
  pages     = {291-298},
  ee        = {http://doi.acm.org/10.1145/1148109.1148159},
  crossref  = {DBLP:conf/spaa/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BuchbinderN09a,
  author    = {Niv Buchbinder and
               Joseph Naor},
  title     = {Online Primal-Dual Algorithms for Covering and Packing},
  journal   = {Math. Oper. Res.},
  volume    = {34},
  number    = {2},
  year      = {2009},
  pages     = {270-286},
  ee        = {http://dx.doi.org/10.1287/moor.1080.0363},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BuchbinderN09b,
  author    = {Niv Buchbinder and
               Joseph Naor},
  title     = {The Design of Competitive Online Algorithms via a Primal-Dual
               Approach},
  journal   = {Foundations and Trends in Theoretical Computer Science},
  volume    = {3},
  number    = {2-3},
  year      = {2009},
  pages     = {93-263},
  ee        = {http://dx.doi.org/10.1561/0400000024},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{caceres99,
 author = {R. Caceres and N. Duffield and J. Horowitz and D. Towsley},
 title = {Multicast-based inference of network internal loss characteristics},
 journal = {IEEE Transactions on Information Theory},
 volume = {45},
 year = {1999}
}

@inproceedings{CalinescuKOZ03,
  author    = {Gruia Calinescu and
               Sanjiv Kapoor and
               Alexander Olshevsky and
               Alexander Zelikovsky},
  title     = {Network Lifetime and Power Assignment in ad hoc Wireless
               Networks},
  booktitle = {ESA},
  year      = {2003},
  pages     = {114-126},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=2832{\&}spage=114},
  crossref  = {DBLP:conf/esa/2003},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{CalinescuW06,
  author    = {Gruia Calinescu and
               Peng-Jun Wan},
  title     = {Range Assignment for Biconnectivity and {\it k}-Edge Connectivity
               in Wireless Ad Hoc Networks},
  journal   = {MONET},
  volume    = {11},
  number    = {2},
  year      = {2006},
  pages     = {121-128},
  ee        = {http://dx.doi.org/10.1007/s11036-006-4466-8},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{cantieni05,
 author = {Gion Reto Cantieni and Gianluca Iannaccone and Chadi Barakat and Christophe Diot and Patrick Thiran},
 title = {Reformulating the monitor placement problem: Optimal Network-wide Sampling},
 booktitle = {Intel Research Technical Report},
 month = {February},
 year = {2005},
}

@article{castro04,
 author = {R. Castro and M. Coates and G. Liang and R. Nowak and B. Yu},
 title = {Network tomography: Recent developments},
 journal = {Statistical science},
 volume = {19},
 number = {3},
 year = {2004}
}

@inproceedings{chaudet05,
 author = {Claude Chaudet and Eric Fleury and Isabelle Gu\&\#233;rin Lassous and Herv\&\#233; Rivano and Marie-Emilie Voge},
 title = {Optimal positioning of active and passive monitoring devices},
 booktitle = {CoNEXT'05: Proceedings of the 2005 ACM conference on Emerging network experiment and technology},
 year = {2005},
 isbn = {1-59593-197-X},
 pages = {71--82},
 location = {Toulouse, France},
 doi = {http://doi.acm.org/10.1145/1095921.1095932},
 publisher = {ACM Press},
 address = {New York, NY, USA},
}

@inproceedings{chen04,
 author = {Y. Chen and D. Bindel and H. Song and R. H. Katz},
 title = {An algebraic approach to practical and scaleable overlay network monitoring},
 booktitle = {Proceedings of ACM SIGCOMM},
 year = {2004}
}

@article{ChuzhoyN06,
  author    = {Julia Chuzhoy and
               Joseph Naor},
  title     = {Covering Problems with Hard Capacities},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {2},
  year      = {2006},
  pages     = {498-515},
  ee        = {http://dx.doi.org/10.1137/S0097539703422479},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{claffy99,
 author = {K. Claffy and T.E. Monk and D. McRobb},
 title = {Internet tomography},
 booktitle = {Nature},
 year = {1999},
}

@inproceedings{ClementiPS99,
  author    = {Andrea E. F. Clementi and
               Paolo Penna and
               Riccardo Silvestri},
  title     = {Hardness Results for the Power Range Assignmet Problem in
               Packet Radio Networks},
  booktitle = {RANDOM-APPROX},
  year      = {1999},
  pages     = {197-208},
  crossref  = {DBLP:conf/random/1999},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{ClementiPS00,
  author    = {Andrea E. F. Clementi and
               Paolo Penna and
               Riccardo Silvestri},
  title     = {The Power Range Assignment Problem in Radio Networks on
               the Plane},
  booktitle = {STACS},
  year      = {2000},
  pages     = {651-660},
  ee        = {http://link.springer.de/link/service/series/0558/bibs/1770/17700651.htm},
  crossref  = {DBLP:conf/stacs/2000},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{ClementiPS04,
  author    = {Andrea E. F. Clementi and
               Paolo Penna and
               Riccardo Silvestri},
  title     = {On the Power Assignment Problem in Radio Networks},
  journal   = {MONET},
  volume    = {9},
  number    = {2},
  year      = {2004},
  pages     = {125-140},
  ee        = {http://dx.doi.org/10.1023/B:MONE.0000013624.32948.87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{coates02,
 author = {M. Coates and A. Hero and R. Nowak and B. Yu},
 title = {Internet tomography},
 booktitle = {IEEE Signal Processing Magazine},
 month = {May},
 year = {2002},
}

@inproceedings{cole03,
  author    = {Richard Cole and
               Ramesh Hariharan},
  title     = {A Fast Algorithm for Computing Steiner Edge Connectivity},
  booktitle = {STOC},
  year      = {2003},
  pages     = {167-176},
  ee        = {http://doi.acm.org/10.1145/780542.780568},
  crossref  = {DBLP:conf/stoc/2003},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{CormenLRS01,
  author = {T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein},
  publisher = {MIT Press},
  title = {Introduction to Algorithms},
  year = 2001
}

@inproceedings{Das03,
  author    = {Arindam Kumar Das},
  title     = {Minimum Power Broadcast Trees for Wireless Networks: Integer
               Programming Formulations},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/25_01.PDF},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{DinitzV94,
 author    = {Yefim Dinitz and 
 	      Alek Vainshtein},
 title     = {The connectivity carcass of a vertex subset in a graph and its incremental maintenance},
 booktitle = {STOC},
 year      = {1994},
 pages     = {716-725},
 ee        = {http://doi.acm.org/10.1145/195058.195442},
 bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{DoyleS84,
	author		= {Peter G. Doyle and Laurie J. Snell},
	title			= {Random Walks and Electric Networks},
	publisher	= {Carus Mathematical Monographs},
	year			= {1984},
}
    
@inproceedings{duffield00,
  author    = {Nick G. Duffield and
               Francesco Lo Presti},
  title     = {Multicast Inference of Packet Delay Variance at Interior
               Network Links},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2000},
  pages     = {1351-1360},
}

@inproceedings{duffield01,
 author = {Nick G. Duffield and Joseph Horowitz and Francesco Lo Presti and Donald F. Towsley},
 title = {Network Delay Tomography from End-to-End Unicast Measurements},
 booktitle = {IWDC '01: Proceedings of the Thyrrhenian International Workshop on Digital Communications},
 year = {2001},
 isbn = {3-540-42592-6},
 pages = {576--595},
 publisher = {Springer-Verlag},
 address = {London, UK},
}

@inproceedings{duffield03,
  author    = {Nick G. Duffield},
  title     = {Simple network performance tomography},
  booktitle = {Proceedings of IMC},
  year      = {2003},
}

@inproceedings{DuttaJPNRT07,
  author    = {Partha Dutta and
               Sharad Jaiswal and
               Debmalya Panigrahi and
               K. V. M. Naidu and
               Rajeev Rastogi and
               Ajay Kumar Todimala},
  title     = {VillageNet: A low-cost, 802.11-based mesh network for rural
               regions},
  booktitle = {COMSWARE},
  year      = {2007},
  ee        = {http://dx.doi.org/10.1109/COMSWA.2007.382461},
  crossref  = {DBLP:conf/comsware/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{edmonds69,
  author    = {Jack Edmonds},
  title     = {Submodular Functions, Matroids, and Certain Polyhedra},
  booktitle = {Calgary International Conference on Combinatorial Structures and their Application},
  year      = {1969},
  pages     = {69-87}
}

@article{edmonds72,
  author    = {Jack Edmonds},
  title     = {Edge Disjoint Branchings},
  booktitle = {Combinatorial Algorithms},
  year      = {1972},
  pages     = {91-96}
}

@article{Feige98,
  author    = {Uriel Feige},
  title     = {A Threshold of ln {\it n} for Approximating Set Cover},
  journal   = {J. ACM},
  volume    = {45},
  number    = {4},
  year      = {1998},
  pages     = {634-652},
  ee        = {http://doi.acm.org/10.1145/285055.285059},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Frank92,
 author = {Frank, Andr\'{a}s},
 title = {On a theorem of Mader},
 journal = {Discrete Math.},
 volume = {101},
 number = {1-3},
 year = {1992},
 issn = {0012-365X},
 pages = {49--57},
 doi = {http://dx.doi.org/10.1016/0012-365X(92)90589-8},
 publisher = {Elsevier Science Publishers B. V.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 }

@inproceedings{FreundS96,
  author    = {Yoav Freund and
               Robert E. Schapire},
  title     = {Game Theory, On-Line Prediction and Boosting},
  booktitle = {COLT},
  year      = {1996},
  pages     = {325-332},
  ee        = {http://doi.acm.org/10.1145/238061.238163},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{gabow91,
  author    = {Harold N. Gabow},
  title     = {Applications of a Poset Representation to Edge Connectivity
               and Graph Rigidity},
  booktitle = {FOCS},
  year      = {1991},
  pages     = {812-821},
}

@article{gabow95,
  author    = {Harold N. Gabow},
  title     = {A Matroid Approach to Finding Edge Connectivity and Packing
               Arborescences},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {50},
  number    = {2},
  year      = {1995},
  pages     = {259-273},
}

@book{garey90,
 author = {Michael R. Garey and David S. Johnson},
 title = {Computers and Intractability; A Guide to the Theory of NP-Completeness},
 year = {1990},
 isbn = {0716710455},
 publisher = {W. H. Freeman \& Co.},
 address = {New York, NY, USA},
}

@article{GoldbergR98,
  author    = {Andrew V. Goldberg and
               Satish Rao},
  title     = {Beyond the Flow Decomposition Barrier},
  journal   = {J. ACM},
  volume    = {45},
  number    = {5},
  year      = {1998},
  pages     = {783-797},
  ee        = {http://doi.acm.org/10.1145/290179.290181},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{goldberg99,
  author    = {Andrew V. Goldberg and
               Satish Rao},
  title     = {Flows in Undirected Unit Capacity Networks},
  journal   = {SIAM J. Discrete Math.},
  volume    = {12},
  number    = {1},
  year      = {1999},
  pages     = {1-5},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/33103},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{goldberg01,
  author    = {Andrew V. Goldberg and
               Kostas Tsioutsiouliklis},
  title     = {Cut Tree Algorithms: An Experimental Study},
  journal   = {J. Algorithms},
  volume    = {38},
  number    = {1},
  year      = {2001},
  pages     = {51-83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{GomoryH61,
  author    = {R. E. Gomory and T. C. Hu},
  title     = {Multi-terminal network flows},
  journal   = {J. Soc. Indust. Appl. Math.},
  volume    = {9},
  number    = {4},
  year      = {1961},
  pages     = {551-570}
}

@article{Graham66,
	author = {R. L. Graham},
	title = {Bounds for certain multiprocessing anomalies},
	journal = {Siam Journal on Applied Mathematics},
	year = {1966},
}

@article{Graham69,
    author = {R. L. Graham},
    title = {Bounds on Multiprocessing Timing Anomalies},
    journal = {SIAM Journal on Applied Mathematics},
    year = {1969},
    volume = {17},
    pages = {416--429}
}

@article{GuhaK98,
  author    = {Sudipto Guha and
               Samir Khuller},
  title     = {Approximation Algorithms for Connected Dominating Sets},
  journal   = {Algorithmica},
  volume    = {20},
  number    = {4},
  year      = {1998},
  pages     = {374-387},
  ee        = {http://dx.doi.org/10.1007/PL00009201},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{gusfield90,
  author    = {Dan Gusfield},
  title     = {Very Simple Methods for All Pairs Network Flow Analysis},
  journal   = {SIAM J. Comput.},
  volume    = {19},
  number    = {1},
  year      = {1990},
  pages     = {143-155},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{HajiaghayiIM07,
  author    = {Mohammad Taghi Hajiaghayi and
               Nicole Immorlica and
               Vahab S. Mirrokni},
  title     = {Power optimization in fault-tolerant topology control algorithms
               for wireless multi-hop networks},
  journal   = {IEEE/ACM Trans. Netw.},
  volume    = {15},
  number    = {6},
  year      = {2007},
  pages     = {1345-1358},
  ee        = {http://doi.acm.org/10.1145/1373476.1373487},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{HajiaghayiKMN07,
  author    = {Mohammad Taghi Hajiaghayi and
               Guy Kortsarz and
               Vahab S. Mirrokni and
               Zeev Nutov},
  title     = {Power optimization for connectivity problems},
  journal   = {Math. Program.},
  volume    = {110},
  number    = {1},
  year      = {2007},
  pages     = {195-208},
  ee        = {http://dx.doi.org/10.1007/s10107-006-0057-5},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{HalldorssonHR01,
 author = {Bjarni V. Halld\'orsson and Magn\'us M. Halld\'orsson and R. Ravi},
 title = {On the Approximability of the Minimum Test Collection Problem},
 booktitle = {ESA '01: Proceedings of the 9th Annual European Symposium on Algorithms},
 year = {2001},
 isbn = {3-540-42493-8},
 pages = {158--169},
 publisher = {Springer-Verlag},
 address = {London, UK},
}

@book{Harary69,
 author = {Frank Harary},
 title = {Graph Theory},
 year = {1969},
 publisher = {Addison-Wesley},
}

@article{HarelT84,
  author    = {Dov Harel and
               Robert Endre Tarjan},
  title     = {Fast Algorithms for Finding Nearest Common Ancestors},
  journal   = {SIAM J. Comput.},
  volume    = {13},
  number    = {2},
  year      = {1984},
  pages     = {338-355},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{hariharan07,
  author    = {Ramesh Hariharan and
               Telikepalli Kavitha and
               Debmalya Panigrahi},
  title     = {Efficient Algorithms for Computing All Low $s-t$ Edge Connectivities and
               Related Problems},
  booktitle = {SODA},
  year      = {2007},
  pages     = {127-136}
}

@inproceedings{hu04,
 author = {Ningning Hu and Li (Erran) Li and Zhuoqing Morley Mao and Peter Steenkiste and Jia Wang},
 title = {Locating internet bottlenecks: algorithms, measurements, and implications},
 booktitle = {SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications},
 year = {2004},
 isbn = {1-58113-862-8},
 pages = {41--54},
 location = {Portland, Oregon, USA},
 doi = {http://doi.acm.org/10.1145/1015467.1015474},
 publisher = {ACM Press},
 address = {New York, NY, USA},
}

@inproceedings{horton03,
 author = {Joseph D. Horton and Alejandro L\'opez-Ortiz},
 title = {On the number of distributed measurement points for network tomography},
 booktitle = {IMC '03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement},
 year = {2003},
 isbn = {1-58113-773-7},
 pages = {204--209},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }

@inproceedings{jamin00,
 author = {S. Jamin and C. Jin and Y. Jin and D. Raz and Y. Shavitt and L. Zhang},
 title = {On the placement of internet instrumentation},
 booktitle = {Proceedings of IEEE INFOCOM},
 month = {April},
 year = {2000},
}

@article{KachitvichyanukulS88,
 author = {Kachitvichyanukul, Voratas and Schmeiser, Bruce W.},
 title = {Binomial random variate generation},
 journal = {Commun. ACM},
 volume = {31},
 number = {2},
 year = {1988},
 issn = {0001-0782},
 pages = {216--222},
 doi = {http://doi.acm.org/10.1145/42372.42381},
 publisher = {ACM},
 address = {New York, NY, USA},
 }


@inproceedings{KaplanST02,
  author    = {Haim Kaplan and
               Nira Shafrir and
               Robert Endre Tarjan},
  title     = {Union-find with deletions},
  booktitle = {SODA},
  year      = {2002},
  pages     = {19-28},
  ee        = {http://doi.acm.org/10.1145/545381.545384},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KangP05a,
  author    = {Intae Kang and
               Radha Poovendran},
  title     = {Maximizing Network Lifetime of Broadcasting Over Wireless
               Stationary Ad Hoc Networks},
  journal   = {MONET},
  volume    = {10},
  number    = {6},
  year      = {2005},
  pages     = {879-896},
  ee        = {http://dx.doi.org/10.1007/s11036-005-4445-5},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{KangP05b,
  author    = {Intae Kang and
               Radha Poovendran},
  title     = {Iterated Local Optimization for Minimum Energy Broadcast},
  booktitle = {WiOpt},
  year      = {2005},
  pages     = {332-341},
  ee        = {http://csdl.computer.org/comp/proceedings/wiopt/2005/2267/00/22670332abs.htm},
  crossref  = {DBLP:conf/wiopt/2005},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}




@inproceedings{Karger93,
  author    = {David R. Karger},
  title     = {Global Min-cuts in RNC, and Other Ramifications of a Simple
               Min-Cut Algorithm},
  booktitle = {SODA},
  year      = {1993},
  pages     = {21-30},
  ee        = {http://doi.acm.org/10.1145/313559.313605},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{Karger94a,
  author    = {David R. Karger},
  title     = {Random sampling in cut, flow, and network design problems},
  booktitle = {STOC},
  year      = {1994},
  pages     = {648-657},
  ee        = {http://doi.acm.org/10.1145/195058.195422},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Karger94b,
  author    = {David R. Karger},
  title     = {Using Randomized Sparsification to Approximate Minimum Cuts},
  booktitle = {SODA},
  year      = {1994},
  pages     = {424-432},
  ee        = {http://doi.acm.org/10.1145/314464.314582},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{karger00,
  author    = {David R. Karger},
  title     = {Minimum cuts in near-linear time},
  journal   = {J. ACM},
  volume    = {47},
  number    = {1},
  year      = {2000},
  pages     = {46-76},
}

@inproceedings{KargerL98,
  author    = {David R. Karger and
               Matthew S. Levine},
  title     = {Finding Maximum Flows in Undirected Graphs Seems Easier
               than Bipartite Matching},
  booktitle = {STOC},
  year      = {1998},
  pages     = {69-78},
  ee        = {http://doi.acm.org/10.1145/276698.276714},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Karger99,
  author    = {David R. Karger},
  title     = {A Randomized Fully Polynomial Time Approximation Scheme
               for the All-Terminal Network Reliability Problem},
  journal   = {SIAM J. Comput.},
  volume    = {29},
  number    = {2},
  year      = {1999},
  pages     = {492-514},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KargerS96,
  author    = {David R. Karger and
               Clifford Stein},
  title     = {A New Approach to the Minimum Cut Problem},
  journal   = {J. ACM},
  volume    = {43},
  number    = {4},
  year      = {1996},
  pages     = {601-640},
  ee        = {http://doi.acm.org/10.1145/234533.234534},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KhandekarRV09,
  author    = {Rohit Khandekar and
               Satish Rao and
               Umesh V. Vazirani},
  title     = {Graph partitioning using single commodity flows},
  journal   = {J. ACM},
  volume    = {56},
  number    = {4},
  year      = {2009},
  ee        = {http://doi.acm.org/10.1145/1538902.1538903},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KleinR95,
  author    = {Philip N. Klein and
               R. Ravi},
  title     = {A Nearly Best-Possible Approximation Algorithm for Node-Weighted
               Steiner Trees},
  journal   = {J. Algorithms},
  volume    = {19},
  number    = {1},
  year      = {1995},
  pages     = {104-115},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Korman05,
	author	= {Simon Korman},
	title	= {On the use of randomization in the online set cover problem},
	journal	= {M.S. thesis, Weizmann Institute of Science},
	year	= {2005}
}

@inproceedings{KortsarzMNT08,
  author    = {Guy Kortsarz and
               Vahab S. Mirrokni and
               Zeev Nutov and
               Elena Tsanko},
  title     = {Approximating Minimum-Power Degree and Connectivity Problems},
  booktitle = {LATIN},
  year      = {2008},
  pages     = {423-435},
  ee        = {http://dx.doi.org/10.1007/978-3-540-78773-0_37},
  crossref  = {DBLP:conf/latin/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KortsarzN09,
  author    = {Guy Kortsarz and
               Zeev Nutov},
  title     = {Approximating minimum-power edge-covers and 2, 3-connectivity},
  journal   = {Discrete Applied Mathematics},
  volume    = {157},
  number    = {8},
  year      = {2009},
  pages     = {1840-1847},
  ee        = {http://dx.doi.org/10.1016/j.dam.2008.12.001},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{kumar04,
 author = {Ritesh Kumar and Jasleen Kaur},
 title = {Efficient Beacon Placement for Network Tomography},
 booktitle = {IMC '04: Proceedings of the 4th ACM SIGCOMM conference on Internet measurement},
 year = {2004},
 isbn = {1-58113-821-0},
 pages = {181--186},
 publisher = {ACM Press},
 address = {New York, NY, USA},
}

@book{kurose05,
 author = {James F. Kurose and Keith W. Ross},
 title = {Computer Networking: A Top-Down Approach Featuring the Internet Package, 3rd edition},
 year = {2005},
 publisher = {Addison-Wesley Longman Publishing Co., Inc.},
}

@inproceedings{LandoN07,
  author    = {Yuval Lando and
               Zeev Nutov},
  title     = {On Minimum Power Connectivity Problems},
  booktitle = {ESA},
  year      = {2007},
  pages     = {87-98},
  ee        = {http://dx.doi.org/10.1007/978-3-540-75520-3_10},
  crossref  = {DBLP:conf/esa/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{LandoN10,
  author    = {Yuval Lando and
               Zeev Nutov},
  title     = {On minimum power connectivity problems},
  journal   = {J. Discrete Algorithms},
  volume    = {8},
  number    = {2},
  year      = {2010},
  pages     = {164-173},
  ee        = {http://dx.doi.org/10.1016/j.jda.2009.03.002},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{li06,
  author    = {Fei Li and Marina Thottan},
  title     = {End-to-end service quality measurement using source-routed probes},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2006}
}

@inproceedings{LiK11,
  author    = {Jian Li and
               Samir Khuller},
  title     = {Generalized Machine Activation Problems},
  booktitle = {SODA},
  year      = {2011},
  pages     = {80-94},
  ee        = {http://www.siam.org/proceedings/soda/2011/SODA11_007_lij.pdf},
  crossref  = {DBLP:conf/soda/2011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{KhullerLS10,
  author    = {Samir Khuller and
               Jian Li and
               Barna Saha},
  title     = {Energy Efficient Scheduling via Partial Shutdown},
  booktitle = {SODA},
  year      = {2010},
  pages     = {1360-1372},
  ee        = {http://www.siam.org/proceedings/soda/2010/SODA10_110_khullers.pdf},
  crossref  = {DBLP:conf/soda/2010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{Liang02,
  author    = {Weifa Liang},
  title     = {Constructing minimum-energy broadcast trees in wireless
               ad hoc networks},
  booktitle = {MobiHoc},
  year      = {2002},
  pages     = {112-122},
  ee        = {http://doi.acm.org/10.1145/513800.513815},
  crossref  = {DBLP:conf/mobihoc/2002},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{LittlestoneW94,
  author    = {Nick Littlestone and
               Manfred K. Warmuth},
  title     = {The Weighted Majority Algorithm},
  journal   = {Inf. Comput.},
  volume    = {108},
  number    = {2},
  year      = {1994},
  pages     = {212-261},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{LenstraST90,
  author    = {Jan Karel Lenstra and
               David B. Shmoys and
               {\'E}va Tardos},
  title     = {Approximation Algorithms for Scheduling Unrelated Parallel
               Machines},
  journal   = {Math. Program.},
  volume    = {46},
  year      = {1990},
  pages     = {259-271},
  ee        = {http://dx.doi.org/10.1007/BF01585745},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{lovasz74,
	author 		= {L\'aszl\'o Lov\'asz},
	title			= {Lecture},
	booktitle	= {Conference of Graph Theory},
	year			= {1974}
}

@book{lovasz93,
	author 		= {L\'aszl\'o Lov\'asz},
	title			= {Combinatorial Problems and Exercises, 2nd ed.},
	year			= {1993},
	publisher	= {North Holland},
}

@article{Mader78,
	author		= {Wolfgang Mader},
	title			=	{A reduction method for edge-connectivity in graphs},
	journal		= {Ann. Discrete Math.},
	volume		= {3},
	year			= {1978},
	pages			= {145-164}
}

@article{Mader82,
	author		= {Wolfgang Mader},
	title			=	{Konstruktion aller n-fach kantenzusammenhangenden Di-graphen},
	journal		= {European J. Combin.},
	volume		= {3},
	year			= {1982},
	pages			= {63-67}
}

@inproceedings{markopoulou04,
  author = "A. Markopoulou and G. Iannaccone and S. Bhattacharyya and C. Chuah and
    C. Diot",
  title = "Characterization of Failures in an {IP} Backbone",
  booktitle = {Proceedings of IEEE INFOCOM},
  address = {Hong Kong, China},
  month = {March},
  year = "2004",
}

@inproceedings{MarksDEAG02,
  author    = {Robert J. Marks II and
               Arindam Kumar Das and
               Mohamed A. El-Sharkawi and
               Payman Arabshahi and
               Andrew Gray},
  title     = {Minimum power broadcast trees for wireless networks: optimizing
               using the viability lemma},
  booktitle = {ISCAS (1)},
  year      = {2002},
  pages     = {273-276},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/ISCAS.2002.1009830},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{moon99,
 author = {Sue Moon and Paul Skelley and Don Towsley},
 title = {Estimation and removal of clock skew from network delay measurements},
 booktitle = {Proceedings of IEEE INFOCOM},
 address = {New York, NY},
 month = {March},
 year = {1999}
}

@book{MotwaniR97,
  author = {R. Motwani and P. Raghavan},
  publisher = {Cambridge University Press},
  title = {Randomized Algorithms},
  year = {1997}
}


@article{NagamochiI92a,
  author    = {Hiroshi Nagamochi and
               Toshihide Ibaraki},
  title     = {A Linear-Time Algorithm for Finding a Sparse k-Connected
               Spanning Subgraph of a k-Connected Graph},
  journal   = {Algorithmica},
  volume    = {7},
  number    = {5{\&}6},
  year      = {1992},
  pages     = {583-596},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{NagamochiI92b,
  author    = {Hiroshi Nagamochi and
               Toshihide Ibaraki},
  title     = {Computing Edge-Connectivity in Multigraphs and Capacitated
               Graphs},
  journal   = {SIAM J. Discrete Math.},
  volume    = {5},
  number    = {1},
  year      = {1992},
  pages     = {54-66},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{nguyen04,
 author = "H. Nguyen and P. Thiran",
 title = "Active measurement for multiple link failures: Diagnosis in {IP} networks",
 booktitle = {Proceedings of Passive and Active Measurement Workshop 2004 (PAM 2004)},
 month = {April},
 year = {2004},
}

@inproceedings{nguyen05,
author = {Hung X. Nguyen and Patrick Thiran},
title = {Binary Versus Analogue Path Monitoring in {IP} Networks},
booktitle = {Lecture Notes in Computer Science, Volume 3431},
month = {January},
year = {2005},
pages = {97},
}

@inproceedings{nguyen06,
author = {Hung Nguyen and Patrick Thiran},
title = {Using End-to-End Data to Infer Lossy Links in Sensor Networks},
booktitle = {Proceedings of IEEE INFOCOM},
month = {April},
year =  {2006},
address = {Barcelona},
}

@article{norros95,
 author = {I. Norros},
 title = {On the use of fractional brownian motion in the theory of connectionless networks},
 journal = {IEEE Journal on Selected Areas in Communications},
 volume = {13},
 number = {6},
 year = {1995}
}

@inproceedings{Nutov06,
  author    = {Zeev Nutov},
  title     = {Approximating Minimum Power Covers of Intersecting Families
               and Directed Connectivity Problems},
  booktitle = {APPROX-RANDOM},
  year      = {2006},
  pages     = {236-247},
  ee        = {http://dx.doi.org/10.1007/11830924_23},
  crossref  = {DBLP:conf/approx/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Nutov08,
  author    = {Zeev Nutov},
  title     = {Approximating Minimum-Power k-Connectivity},
  booktitle = {ADHOC-NOW},
  year      = {2008},
  pages     = {86-93},
  ee        = {http://dx.doi.org/10.1007/978-3-540-85209-4_7},
  crossref  = {DBLP:conf/adhoc-now/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Nutov10,
  author    = {Zeev Nutov},
  title     = {Approximating Minimum-Power k-Connectivity},
  journal   = {Ad Hoc {\&} Sensor Wireless Networks},
  volume    = {9},
  number    = {1-2},
  year      = {2010},
  pages     = {129-137},
  ee        = {http://www.oldcitypublishing.com/AHSWN/AHSWN9.1-2abstracts/AHSWNv9n1-2p129-137Nutov.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{padmanabhan03,
  author    = {V. N. Padmanabhan and L. Qiu and H. J. Wang},
  title     = {Server-based inference of internet performance},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2003},
}

@inproceedings{PanigrahiDJNR08,
  author    = {Debmalya Panigrahi and
               Partha Dutta and
               Sharad Jaiswal and
               K. V. M. Naidu and
               Rajeev Rastogi},
  title     = {Minimum Cost Topology Construction for Rural Wireless Mesh
               Networks},
  booktitle = {INFOCOM},
  year      = {2008},
  pages     = {771-779},
  ee        = {http://dx.doi.org/10.1109/INFOCOM.2008.128},
  crossref  = {DBLP:conf/infocom/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{papagiannaki02,
 author = {K. Papagiannaki and S. Moon and C. Fraleigh and P. Thiran and F. Tobagi and C. Diot},
 title = {Analysis of measured single-hop delay from an operational backbone network},
 booktitle = {Proceedings of IEEE INFOCOM},
 year = {2002}
}

@inproceedings{paxson98,
    author = "Vern Paxson",
    title = "On Calibrating Measurements of Packet Transit Times",
    booktitle = "Measurement and Modeling of Computer Systems",
    pages = "11-21",
    year = "1998",
    url = "citeseer.ist.psu.edu/paxson98calibrating.html"
}

@inproceedings{reddy00,
 author = {Anoop Reddy and Ramesh Govindan and Deborah Estrin},
 title = {Fault isolation in multicast trees},
 booktitle = {SIGCOMM '00: Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication},
 year = {2000},
 isbn = {1-58113-223-9},
 pages = {29--40},
 publisher = {ACM Press},
 address = {New York, NY, USA},
}

@article{schieber88,
  author    = {Baruch Schieber and
               Uzi Vishkin},
  title     = {On Finding Lowest Common Ancestors: Simplification and Parallelization},
  journal   = {SIAM J. Comput.},
  volume    = {17},
  number    = {6},
  year      = {1988},
  pages     = {1253-1262},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{SenR07,
  author    = {Sayandeep Sen and
               Bhaskaran Raman},
  title     = {Long distance wireless mesh network planning: problem formulation
               and solution},
  booktitle = {WWW},
  year      = {2007},
  pages     = {893-902},
  ee        = {http://doi.acm.org/10.1145/1242572.1242693},
  crossref  = {DBLP:conf/www/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Sgall96,
  author    = {Jiri Sgall},
  title     = {On-line Scheduling},
  booktitle = {Online Algorithms},
  year      = {1996},
  pages     = {196-231},
  ee        = {http://dx.doi.org/10.1007/BFb0029570},
  crossref  = {DBLP:conf/dagstuhl/1996oa},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{shavitt01,
  author    = {Y. Shavitt and X. Sun and A. Wool and B. Yener},
  title     = {Computing the unmeasured: An algebraic approach to internet mapping},
  booktitle = {Proceedings of IEEE INFOCOM},
  year      = {2001}
}

@inproceedings{Sherman09,
  author    = {Jonah Sherman},
  title     = {Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations
               to Sparsest Cut},
  booktitle = {FOCS},
  year      = {2009},
  pages     = {363-372},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2009.66},
  crossref  = {DBLP:conf/focs/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{shih01,
 author = {Meng-Fu Shih and Alfred Hero},
 title = {Unicast Inference of Network Link Delay Distributions from Edge Measurements},
 booktitle = {In Proc. IEEE Int. Conf. on Acoust., Speech and Signal Proc.},
 month = {May},
 year = {2001},
}

@article{ShmoysT93,
  author    = {David B. Shmoys and
               {\'E}va Tardos},
  title     = {An approximation algorithm for the generalized assignment
               problem},
  journal   = {Math. Program.},
  volume    = {62},
  year      = {1993},
  pages     = {461-474},
  ee        = {http://dx.doi.org/10.1007/BF01585178},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{SleatorT83,
  author    = {Daniel Dominic Sleator and
               Robert Endre Tarjan},
  title     = {A Data Structure for Dynamic Trees},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {26},
  number    = {3},
  year      = {1983},
  pages     = {362-391},
}

@inproceedings{SpielmanT04,
  author    = {Daniel A. Spielman and
               Shang-Hua Teng},
  title     = {Nearly-linear time algorithms for graph partitioning, graph
               sparsification, and solving linear systems},
  booktitle = {STOC},
  year      = {2004},
  pages     = {81-90},
  ee        = {http://doi.acm.org/10.1145/1007352.1007372},
  crossref  = {DBLP:conf/stoc/2004},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{SpielmanT06,
  author    = {Daniel A. Spielman and
               Shang-Hua Teng},
  title     = {Nearly-Linear Time Algorithms for Preconditioning and Solving
               Symmetric, Diagonally Dominant Linear Systems},
  journal   = {CoRR},
  volume    = {abs/cs/0607105},
  year      = {2006},
  ee        = {http://arxiv.org/abs/cs/0607105},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{SpielmanS08,
  author    = {Daniel A. Spielman and
               Nikhil Srivastava},
  title     = {Graph sparsification by effective resistances},
  booktitle = {STOC},
  year      = {2008},
  pages     = {563-568},
  ee        = {http://doi.acm.org/10.1145/1374376.1374456},
  crossref  = {DBLP:conf/stoc/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@book{stallings99,
 author = {W. Stallings},
 title = {SNMP, SNMPv2, SNMPv3, and RMON 1 and 2},
 publisher = {Addison-Wesley Longman, Inc.},
 year = {1999},
 edition = {Third},
}

@inproceedings{suh05,
 author = {K. Suh and Y. Guo and J. Kurose and D. Towsley},
 title = {Locating network monitors: Complexity, heuristics and coverage},
 booktitle = {Proceedings of IEEE INFOCOM},
 month = {March},
 year = {2005},
}

@article{Szigeti08,
  author    = {Zolt{\'a}n Szigeti},
  title     = {Edge-splittings preserving local edge-connectivity of graphs},
  journal   = {Discrete Applied Mathematics},
  volume    = {156},
  number    = {7},
  year      = {2008},
  pages     = {1011-1018},
  ee        = {http://dx.doi.org/10.1016/j.dam.2007.05.046},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{TanZLZ06,
  author    = {Liansheng Tan and
               Xiaoli Zhan and
               Jie Li and
               Fuzhe Zhao},
  title     = {A novel tree-based broadcast algorithm for wireless ad hoc
               networks},
  journal   = {IJWMC},
  volume    = {1},
  number    = {2},
  year      = {2006},
  pages     = {156-162},
  ee        = {http://dx.doi.org/10.1504/IJWMC.2006.012475},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{tsang01,
 author = {Yolanda Tsang and Mark Coates and Robert Nowak},
 title = {Passive Network Tomography Using {EM} Algorithms},
 booktitle = {In Proc. IEEE Int. Conf. Acoust., Speech and Signal Proc., volume 2},
 month = {May},
 year = {2001},
}

@book{Vazirani01,
 author = {V. Vazirani},
 title = {Approximation algorithms},
 year = {2001},
 publisher = {Springer-Verlag, Berlin},
}

@article{Wolsey82,
  author    = {Laurence A. Wolsey},
  title     = {An analysis of the greedy algorithm for the submodular set
               covering problem},
  journal   = {Combinatorica},
  volume    = {2},
  number    = {4},
  year      = {1982},
  pages     = {385-393},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{williamson95,
 author = {David P. Williamson and 
           Michel X. Goemans and
	   Milena Mihail and 
	   Vijay V. Vazirani},
 title = {A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems},
 journal = {Combinatorica},
 volume = {15},
 number = {3},
 year = {1995},
 pages = {435-454},
 bibsource = {DBLP, http://dblp.uni-trier.de}
}

